package com.duoduo.algs4.DataStructure;

import java.util.Iterator;
import java.util.NoSuchElementException;

import edu.princeton.cs.introcs.StdIn;
import edu.princeton.cs.introcs.StdOut;

public class Bag<Item> implements Iterable<Item> {

	private int N;
	private Node first;

	private class Node {
		private Item item;
		private Node next;
	}

	public Bag() {
		first = null;
		N = 0;
		assert check();

	}

	public boolean isEmpty() {
		return first == null;

	}

	public void add(Item item) {
		Node node = new Node();
		node.item = item;
		node.next = first;
		first = node;
		N++;
		assert check();

	}

	public int size() {
		return N;
	}

	// check internal invariants
	private boolean check() {
		if (N == 0) {
			if (first != null)
				return false;
		} else if (N == 1) {
			if (first == null)
				return false;
			if (first.next != null)
				return false;
		} else {
			if (first.next == null)
				return false;
		}

		// check internal consistency of instance variable N
		int numberOfNodes = 0;
		for (Node x = first; x != null; x = x.next) {
			numberOfNodes++;
		}
		if (numberOfNodes != N)
			return false;

		return true;
	}

	public Iterator<Item> iterator() {
		return new ListIterator();
	}

	private class ListIterator implements Iterator<Item> {
		private Node current = first;

		public boolean hasNext() {
			return current != null;
		}

		public Item next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			Item item = current.item;
			current = current.next;
			return item;
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}

	}

	public static void main(String[] args) {
		Bag<String> bag = new Bag<String>();
		while (!StdIn.isEmpty()) {
			String item = StdIn.readString();
			bag.add(item);
		}

		StdOut.println("size of bag = " + bag.size());
		for (String s : bag) {
			StdOut.println(s);
		}
	}
}
